//
//  insertion-sort.cpp
//  
//
//  Created by 茂杰 汤 on 12-4-16.
//  Copyright (c) 2012年 清华大学. All rights reserved.
//

#include <iostream>

using namespace std;

const int arraySize = 8;
const int MAX = 1 << 31 - 1;

void merge(int array[], int p, int q, int r);
void mergeSort(int array[], int p, int r);

int main()
{
	int a[arraySize] = {2, 4, 5, 7, 1, 2, 3, 6};
	mergeSort(a, 0, 7);
	for (int i = 0; i < arraySize; ++i) {
		cout << a[i] << " ";
	}
	cout << endl;
	return 0;
}

// 升序
// A[p..q], A[q+1..r]
void merge(int array[], int p, int q, int r)
{
	int n1 = q-p+1;
	int n2 = r-q;
	int leftArray[arraySize];
	memset(leftArray, 0, sizeof(leftArray));
	for (int i = 0; i < n1; ++i) {
		leftArray[i] = array[p+i];
	}
	leftArray[n1] = MAX;
	int rightArray[arraySize];
	memset(rightArray, 0, sizeof(rightArray));
	for (int i = 0; i < n2; ++i) {
		rightArray[i] = array[q+1+i];
	}
	rightArray[n2] = MAX;
	int i = 0;
	int j = 0;
	for (int k = p; k <= r; ++k) {
		if (leftArray[i] <= rightArray[j]) {
			array[k] = leftArray[i];
			i++;
		} else {
			array[k] = rightArray[j];
			j++;
		}
	}
}

// 升序
// A[p..r]
void mergeSort(int array[], int p, int r)
{
	if (p < r) {
		int q = (p+r)/2;
		mergeSort(array, p, q);
		mergeSort(array, q+1, r);
		merge(array, p, q, r);
	}
}